// m

// 实现前缀树数据结构的相关类Tries类

// Trie类
// Trie()初始化前缀对象
// void insert(String word)，向前缀树中插入字符串word
// boolean search(String word)，如果字符串word在前缀树中，返回true，否则返回false
// boolean startWith(prefix),如果之前已经插入的字符串word的前缀为prefix，返回true，否则返回false

// 思路1， 前缀树（字典树）
// 前缀树是一颗多叉树，其中每个节点包含指向子节点的指针数组children，以及布尔变量isEnd，children用于存储当前字符节点，一般长度为所含字符种类个数，可以使用
// 哈希表代替指针数组，isEnd用于判断该节点是否为字符串的结尾

// 插入字符串
//

function Node() {
    this.children = new Map()
    this.isEnd = false
}

function Trie() {
    this.root = new Node()
}

Trie.prototype.insert = function (word) {
    let cur = this.root 
    for (let i = 0; i < word.length; i++) {
        if (!cur.children.has(word[i])) {
            cur.children.set(word[i], new Node())
        }        
        cur = cur.children.get(word[i])
    }
    cur.isEnd = true
}

Trie.prototype.search = function (word) {
    let cur = this.root
    for (let i = 0; i < word.length; i++) {
        if (!cur.children.has(word[i])) {
            return false
        }        
        cur = cur.children.get(word[i])
    }
    return cur && cur.isEnd
}

Trie.prototype.startsWith = function (prefix) {
    let cur = this.root
    for (let i = 0; i < prefix.length; i++) {
        if (!cur.children.has(prefix[i])) {
            return false
        }
        cur = cur.children.get(prefix[i])
    }
    return !!cur
}

const trie = new Trie()
console.log(trie.insert('apple'));
console.log(trie.search('apple'))